#include <climits>
#include <cstdio>

int max(int a, int b);
struct good_info {
    int weight;
    int value;
} data_info[101];
int dp[101][1001];

int main(int argc, char const* argv[])
{
    int s, n;
    while (scanf("%d%d", &s, &n) != EOF) {
        for (int i = 1; i <= n; i++)
            scanf("%d%d", &data_info[i].weight, &data_info[i].value);
        for (int i = 0; i <= s; i++)
            dp[0][i] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= s; j++) {
                if (j < data_info[i].weight)
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - data_info[i].weight] + data_info[i].value);
            }
        }
        printf("%d\n", dp[n][s]);
    }
    return 0;
}

int max(int a, int b) { return a > b ? a : b; }